//
// Created by cheng on 2021/01/25.
//

#include <iostream>
#include <vector>

using namespace std;

long long cnt;

void InsertionSort(vector<int>& arr, int g);
void shellSort(vector<int>& arr, vector<int>& G);

int main() {
    vector<int> arr = {9,8,7,6,5,4,3,2,1};
    vector<int> G;
    cout << "arr: ";
    for(auto item : arr) {
        cout << item << " ";
    }
    cout << endl;
    shellSort(arr, G);
    cout << "G: size = " << G.size() << ", content: ";
    for (auto it = G.end()-1; it >= G.begin(); it--) {
        cout << *it << " ";
    }
    cout << endl;
    cout << "cnt: " << cnt << endl;
    cout << "arr: ";
    for(auto item : arr) {
        cout << item << " ";
    }
    return 0;
}

/**
 * 指定间隔的插入排序
 * @param arr 待排数组
 * @param len 数组长度
 * @param g 间隔
 */
void InsertionSort(vector<int>& arr, int g) {
    for (int i = g; i < arr.size(); i++) {
        int v = arr[i];
        int j = i-g;
        while(j >= 0 && arr[j] > v) {
            arr[j + g] = arr[j];
            j-= g;
            cnt++;
        }
        arr[j + g] = v;
    }
}

void shellSort(vector<int>& arr, vector<int>& G) {
    auto h = 1;
    // 设定每次排序的间隔
    while(true) {
        if(h > arr.size()) {
            break;
        }
        G.push_back(h);
        // 排序间隔设定规则
        h = 2*h +1;
    }
    // 开始循环插入排序
    for (auto it = G.end()-1; it >= G.begin(); it--) {
        InsertionSort(arr, *it);
    }
}

